#pragma once
#include <vector>
using namespace std;

namespace countPrimes
{
	class Solution {
	public:
		int countPrimes(int n) {
			if (n < 2)
			{
				return 0;
			}
			vector<bool> flags(n + 1, true);
			for (size_t i = 2; i < n; i++)
			{
				if (flags[i] == false)
				{
					continue;
				}
				for (size_t j = 2 * i; j < n; j += i)
				{
					flags[j] = false;
				}
			}
			int count = 0;
			for (size_t i = 2; i < n; i++)
			{
				if (flags[i])
				{
					count++;
				}
			}
			return count;
		}
	};
}
